A computer network typically comprises a collection of interconnection nodes such as computer systems and switches. These may in turn be connected through an irregular configuration of transmission lines, i.e., links. The switches are specialized computers used to connect two or more links. Data is exchanged among nodes of such an arbitrary topology network by passing packets and messages from switch to switch over the links. Specifically, when a packet or message arrives on an incoming link, the switch decides onto which of the outgoing links that packet will be forwarded.
In a connection-oriented network, a virtual circuit (VC) is commonly established when exchanging packets between nodes of the network. The virtual circuit is a temporary logical path connection that requires a set up procedure to open the virtual circuit prior to transferring the data packets, and a release procedure to close the circuit once the data transfer is complete. This obviates the need for effecting routing decisions for each data packet that is transferred between the nodes once the circuit is opened. For point-to-point communication, the set up procedure creates a virtual circuit by allocating certain switches and links in the network to establish the "best" route, according to conventional route configuration techniques, between a source node and a destination node. However, opening and closing virtual circuits is a time and resource consuming task. Further, there are limits as to how many virtual circuits can be opened and supported simultaneously.
Virtual circuits can also perform point-to-multipoint connections, where one source node connects to several destination nodes. This allows several techniques, including multicasting, which involves transmitting a single multicast packet from a source node and having it received by a group of destination nodes.
One use for multicasting is Distributed Interactive Simulation (DIS) applications. An example of DIS is military training, although DIS technology can be used for training non-military personnel and to construct distributed virtual-reality games. A simulation involving a multitude of actors or objects is set up and maintained in near-real time. Typical objects are tanks, trucks, planes, helicopters, ships, and dismounted infantry (soldiers). In a simulation, a computer is responsible for modeling some number (typically between 1 and 100) entities. Each machine sends packets containing the current state of locally modeled entities, and receives packets containing the current state of remote entities within the region of interest of local entities.
DIS can benefit from IP multicasting in that simulation packets are delivered to only those simulators that need them. Typically, each entity transmits to one multicast group and joins a number of multicast groups. One can imagine a grid in latitude and longitude and sending to a group corresponding to one's location and joining all nearby groups.
One technique for providing multicast is called bilevel multicast. The central idea of bilevel multicast is the construction of a private virtual multicast network using an existing multipoint delivery service. All bilevel multicast routers (BMRs) are peers connected to the multipoint delivery service. More features of bilevel multicast will be discussed below.
There is a need to use more and more multicast groups for DIS and other applications to obtain finer-grained control over data delivery and deliver less unneeded data. There are also constraints which prevent the use of as many multicast groups as are desired. Routers cannot support a very large number of groups. Multicast routing protocols that can handle a very large number of concurrent multicast groups have not yet been developed. Some problems that must be addressed include routing traffic caused by transient joining of groups, the requirement of sufficient router memory to hold multicast routing tables.
Another constraint is the inability of hosts to support a large number of subscribed multicast groups efficiently. There are two common problems: a shortage of hardware filtering slots, so that the network interface delivers all multicast packets to the operating system; and the lack of efficiency of networking code to deal with one hundred or more subscribed groups. Accordingly, efficient delivery of packets to the proper destinations with a minimum of oversent data is very important. Oversent data is data sent to more destinations than it is needed. Further, the system must efficiently use bandwidth to deliver as many packets as possible, while observing packet requirements including priority levels. Obtaining a proper balance of high packet throughput while guaranteeing high-priority packets are not delayed (often referred to as Quality of Service (QoS)) is extremely problematic.
Accordingly, what is needed is a system and method for optimizing a network's virtual circuits (VCs), including minimizing oversent data, and utilizing VC bandwidth for optimum delivery while still maintaining quality of service. Further, the optimizations should perform well with the transient nature of nodes joining and leaving multicast groups, and VCs opening and closing in response to the multicast membership changes.